In this day and age when computers are used in every corner of society and networks such as the Internet are widely used, the storing and processing of large-scale data has become common occurrence.
There has been an effort to develop efficient algorithms for processing large-scale data. Processing that is frequently required when large-scale data, especially large-scale table data, is processed is sorting. As efficient sorting algorithms, radix sort and counting sort (also referred to as distribution counting sort) are known. Counting sort may be utilized for the sorting of each digit in radix sort. Although counting sort is an efficient algorithm, its application is limited by the requirement of the following conditions:
1) objects to be sorted are integers;
2) the upper limit and lower limit of the integers to be sorted are known; and
3) a difference between the upper limit and lower limit of the integers to be sorted is not exceedingly large.
Against this background, the inventor of the present invention has developed a data management mechanism that is suitable for the high-speed searching, summarizing, and sorting of large-scale table data (see Patent Document 1). This data management mechanism uses an information block for representing the individual field values of a field included in table data. In this information block, field values belonging to a field of the table data are represented by field value sequence numbers assigned to the respective field values and an array of the actual field values arranged in an order of field value sequence numbers. An array is provided in which the field value sequence numbers corresponding to the field values of respective records are arranged in the order of record numbers. The field value of a given record is identified by finding the value corresponding to the field value sequence number of this given record in the array of the field values. Further, a record to be processed in table data is identified by use of an array in which record numbers are arranged in sequence.
The information block is a table in which field values corresponding to field value sequence numbers are stored in the order of field value sequence numbers with respect to each field of the table data, wherein the field value sequence numbers represent the sequencing of field values (i.e., assigning integers to field values) belonging to a given field. The field values may be any type of data such as numerical values (integer, fixed point, floating point, or the like) or character strings. This data management mechanism has an advantage in that a value of any data type can be treated as an integer that is a field value sequence number. Namely, when character-string data are to be sorted according to this data management mechanism, for example, character-string data are not the actual sort objects subjected to sorting, but field value sequence numbers corresponding to the values of character-string data are the actual sort objects that are to be sorted. In so doing, the results of sorting are represented by an array in which record numbers are arranged in sequence. In this manner, the information-block-based data management mechanism developed by the inventor of the present invention is advantageous in that the above-noted conditions 1) through 3) required for the application of counting sort are satisfied.
There has also been an effort to introduce parallel processing in order to perform a vast amount of computation at high speed that is necessary for the purpose of processing large-scale data. For the sorting purpose, also, various parallel sorting algorithms have been developed. In general, parallel processing architectures are classified manly into distributed-memory type and shared-memory type. In the case of the distributed-memory type, a system is configured by combining a plurality of processors each having a local memory. In this arrangement, it is possible in theory to design a hardware system incorporating hundreds to tens of thousands of processes. However, the distributed-memory type is fraught with technical problems such as the complexity of distributed data management and the low efficiency of processor-to-processor communication. In the shared-memory type, on the other hand, a plurality of processors share a single large memory space. In this arrangement, traffic between a set of processors and the shared memory becomes bottleneck, so that it is believed to be difficult to implement a system incorporating more than 100 processors in practice.
Against this background, it is now possible to obtain a personal computer that is implemented as a shared-memory multiprocessor system using a plurality of CPUs. Typical CPUs used in such a personal computer operate with internal clock that is five to six times faster than the clock of the memory bus, and are provided with an automatic parallel processing mechanism and pipeline processing mechanism embedded therein, thereby processing one item of data in one clock cycle (i.e., memory bus clock cycle).
[Patent Document 1] International Publication WO00/10103